package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/19
 * @description: 309. 最佳买卖股票时机含冷冻期
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
 * 至此，股票系列应该差不多了
 */
public class B_309_最佳买卖股票时机含冷冻期 {


	public static void main(String[] args) {

	}

	/**
	 * DP 就是需要考虑完整所有的情况
	 * 空间上可以考虑再优化
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {
		int len = prices.length;
		//令 dp[i][0]，dp[i][1]，dp[i][2] 分别表示当前的状态
		//dp[i][0]：当天持股；
		//dp[i][1]：当天持现金（非冷冻，可以今日卖出）；
		//dp[i][2]：当天持现金（冷冻期，明确昨日卖出）
		//那么：
		//dp[i][0] = max(dp[i-1][0],-prices[i])
		//dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
		//dp[i][2] = dp[i-1][1]
		int[][] dp = new int[len][3];
		dp[0][0] = -prices[0];
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
			dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
			dp[i][2] = dp[i - 1][1];
		}
		return dp[len - 1][1];
	}
}
